package main

func main() {

}

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
	if root == nil {
		return [][]int{}
	}
	queue := []*TreeNode{root}
	ans := [][]int{}
	for len(queue) > 0 {
		num := len(queue)
		lq := []int{}
		var node *TreeNode
		for ; num > 0; num-- {
			node = queue[0]
			queue = queue[1:]
			lq = append(lq, node.Val)
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		if len(lq) > 0 {
			ans = append(ans, lq)
			lq = []int{}
		}
	}
	return ans
}
